Bernstein Inequality

Let $X_1,X_2,...,X_k$ be independent random variables with each $X_i \in [-1,1]$. Let $\mu_i = \mathbb{E}[X_i]$ and $\sigma_i^2=\mathrm{Var}[X_i]$. Let $\mu=\sum_i \mu_i$ and $\sigma^2 = \sum_i \sigma_i^2$. Then, for $k \leq \frac{1}{2}\sigma$, $S=\sum_i X_i$ satisfies $$\mathrm{Pr}[|S-\mu| > k \cdot \sigma]\leq 2e^{-\frac{k^2}{4}}$$

Example of Concentration inequality.

Special cases: Chernoff Bound, Hoeffding Inequality, Azuma’s Inequality

References:

• https://en.wikipedia.org/wiki/Bernstein_inequalities_(probability_theory)